package ljl.alg.wangzheng_camp.round1.find_the_law;

import java.util.*;

/**
 * 你正在使用一堆木板建造跳水板。
 * <p>
 * 有两种类型的木板，其中长度较短的木板长度为shorter，
 * 长度较长的木板长度为longer。
 * <p>
 * 你必须正好使用k块木板。编写一个方法，生成跳水板所有可能的长度。
 * <p>
 * 返回的长度需要从小到大排列。
 * <p>
 * 示例 1
 * <p>
 * 输入：
 * shorter = 1
 * longer = 2
 * k = 3
 * 输出： [3,4,5,6]
 * 解释：
 * 可以使用 3 次 shorter，得到结果 3；使用 2 次 shorter 和 1 次 longer，得到结果 4 。
 * 以此类推，得到最终结果。
 */
public class _16_11_diving_board {
    
    /**
     * 我草他妈翻车了
     * 这是简单？我干
     * <p>
     * 我尼玛？
     * <p>
     * 我搞了两个 for 循环
     * for (i in 0..k)
     * for (j in 0..(k-i))
     * 不知道咋想的，不太聪明
     */
    public int[] divingBoard2(int shorter, int longer, int k) {
        if (k == 0) return new int[0];
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i <= k; i++) {
            set.add(shorter * i + longer * (k - i));
        }
        List<Integer> list = new ArrayList<>(set);
        Collections.sort(list);
        int[] res = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }
    
    /**
     * 面试金典里的题。。
     * 还是太莽了，应该认真分析
     *
     * 他用了一个证明，其实想也能大概想出来是这样
     *
     * 考虑以下两种不同的组合：
     * 第一种组合，有 i 块长木板，则跳水板的长度是
     *      shorter × (k − i) + longer × i；
     * 第二种组合，有 j 块长木板，则跳水板的长度是
     *      shorter × (k − j) + longer × j。
     * 其中 0≤ i < j ≤ k。
     * 则两种不同的组合下的跳水板长度之差为：
     *      (shorter × (k − i) + longer × i) − (shorter × (k − j) + longer × j) = (longer − shorter) × (i − j)
     * 由于 longer>shorter 且 i < j，因此上式的值小于 0。
     * 由此可见，任意两种不同的组合下的跳水板长度都是不一样的，而且使用的长木板越多，跳水板的长度越大
     *
     * 确实是简单，但是也没那么简单。。
     */
    public int[] divingBoard(int shorter, int longer, int k) {
        if (k == 0) return new int[0];
        if (shorter == longer) return new int[]{longer * k};
        int[] res = new int[k + 1];
        for (int i = 0; i <= k; i++) {
            res[i] = longer * i + shorter * (k - i);
        }
        return res;
    }
}
